#include "LinkedList.h"
#include <stdio.h>
#include <stdlib.h>
/*
	Create_Node:创建新的数据节点
	@d :数据节点的数据域
	
	返回值：成功 返回新的数据节点的地址
			失败  返回NULL
*/
struct Node*Create_Node(ElemType d)
{
    struct Node* pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return NULL;
    pnew->data = d;
    pnew->next = NULL;

	return pnew;
}
/*
	Create_input_LinkedList:创建一条从键盘上输入数据的整形数据链表
	
	返回值：
		返回的 首节点的地址
*/
struct Node*Create_input_LinkedList()
{
   struct Node* first = NULL;//指向首节点
   struct Node* last = NULL;//指向尾节点
   while(1)
   {
        int d;
        scanf("%d", &d);
        if(d == 0)
            break;
        //创建新节点并赋值
        struct Node*pnew = Create_Node(d);
        if(pnew == NULL)
            return NULL;

        //将新节点增加到链表中
        if(first == NULL && last == NULL)//空链表
        {
            first = last = pnew;
        }
        #if 1
        else//（尾插法）
        {
            last->next = pnew;
            last = pnew;//更新尾节点指针
        }
        #else
        else//头插法
        {
            pnew->next = first;
            first = pnew;//更新首节点指针
        } 
        #endif
   }

   return first;
}
/*
    Print_LinkedList:输出一条整型数据链表
    @first： 指针，指向链表的首节点

    返回值：
        无
*/
void Print_LinkedList(struct Node*first)
{
    printf("==========================\n");
    //if(first == NULL)
    //    return ;
    struct Node*p = first;// 遍历指针
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
/*
	Insert_LinkedList_front:用头插法的方式在first指向的链表中，增加一个元素x
	
	返回值：
		返回的 首节点的地址
*/
struct Node*Insert_LinkedList_front(struct Node*first, ElemType x)
{
    //创建新节点并赋值
    struct Node* pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return first;
    pnew->data = x;
    pnew->next = NULL;

    //头插法方式增加新节点
    if(first == NULL)//空链表
    {
        first = pnew;
        //return pnew;
    }
    else
    {
        pnew->next = first;
        first = pnew;//更新首节点指针
    }

    return first;
}
/*
	Insert_LinkedList_tail:用尾插法的方式的方式在first指向的链表中，增加一个元素x
	
	返回值：
		返回的 首节点的地址
*/
struct Node*Insert_LinkedList_tail(struct Node*first, ElemType x)
{
    //创建新节点并赋值
    struct Node* pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return first;
    pnew->data = x;
    pnew->next = NULL;

    //头插法方式增加新节点
    if(first == NULL)//空链表
    {
        first = pnew;
        //return pnew;
    }
    else
    {
        struct Node*p = first;//遍历指针：查找尾节点
        while(p->next)
        {
            p = p->next;
        }
        p->next = pnew;
    }

    return first;
}

/*
	Insert_node_y:在first指向的链表中，查找节点值为x的节点，在其前面插入一个值为y的节点
	如果没有则增加在最后，如果有多个则找第一个
	返回值：
		返回插入之后链表的首节点地址
*/
struct Node* Insert_node_y(struct Node*first, ElemType x,ElemType y)
{
    //创建新节点并赋值
    struct Node* pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return first;
    pnew->data = y;
    pnew->next = NULL;

    if(first == NULL)
        return pnew;
    //查找再增加
    //查找
    struct Node*p = first;//遍历指针
    struct Node*pre = NULL;//指向遍历指针的前一个节点

    while(p)
    {
        if(p->data == x)
            break;
        pre = p;
        p = p->next;
    }

    //增加
    if(p)//成功找到
    {
        pnew->next = p;
        if(p == first)//首节点
        {
            //pnew->next = p;//pnew->next = first;
            first = pnew;
        }
        else
        {
            //pnew->next = p;
            pre->next = pnew;
        }
    }
    else
    {
        pre->next = pnew;
    }

    return first;
}


/*
	Insert_node_y_behind_x:在first指向的链表中，查找节点值为x的节点，在其后面插入一个值为y的节点
	如果没有则增加在最后，如果有多个则找第一个
	返回值：
		返回插入之后链表的首节点地址
*/
struct Node* Insert_node_y_behind_x(struct Node*first, ElemType x,ElemType y)
{
    //创建新节点并赋值
    struct Node* pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return first;
    pnew->data = y;
    pnew->next = NULL;

    if(first == NULL)
        return pnew;
    //查找再增加
    //查找
    struct Node*p = first;//遍历指针
    struct Node*pre = NULL;//指向遍历指针的前一个节点

    while(p)
    {
        if(p->data == x)
            break;
        pre = p;
        p = p->next;
    }

    if(p)
    {
        pnew->next = p->next;
        p->next = pnew;
    }
    else
    {
        pre->next = pnew;
    }

    return first;
}
/*
	Delete_x_node:在first指向的链表中，查找节点值为x的节点，将其删除
	如果有多个则删除第一个
	返回值：
		返回删除之后链表的首节点地址
*/
struct Node*Delete_x_node(struct Node*first, ElemType x)
{
    //查找
    struct Node*p = first;//遍历指针
    struct Node*pre = NULL;//指向p的前一个
    while(p)
    {
        if(p->data == x)
            break;
        pre = p;
        p = p->next;
    }

    //删除
    if(p)
    {
        if(p == first)
        {
            first = first->next;
            // p->next = NULL;
            // free(p);
            // p = NULL;
        }
        else
        {
            pre->next = p->next;
            // p->next = NULL;
            // free(p);
            // p = NULL;
        }
        p->next = NULL;
        free(p);
        p = NULL;
    }

    return first;
}
/*
	Delete_all_x_node:在first指向的链表中，查找节点值为x的节点，将其删除
	如果有多个则删除所有
	返回值：
		返回删除之后链表的首节点地址
*/
struct Node*Delete_all_x_node(struct Node*first, ElemType x)
{
    //查找
    struct Node*p = first;//遍历指针
    struct Node*pre = NULL;//指向p的前一个
    while(p)
    {  
        while(p)
        {
            if(p->data == x)
                break;
            pre = p;
            p = p->next;
        }

        //删除
        if(p)
        {
            if(p == first)
            {
                first = first->next;
                p->next = NULL;
                free(p);
                p = first;
            }
            else
            {
                pre->next = p->next;
                p->next = NULL;
                free(p);
                p = pre->next;
            }
           
        }
    }
    return first;
}

/*
	Create_sort_LinkedList:从键盘上输入数据，创建一条升序的整型数据链表
	返回值：
		返回新链表的首节点地址
*/
struct Node*Create_sort_LinkedList()
{
    struct Node* first = NULL;//指向首节点
    struct Node* last = NULL;//指向尾节点
    while(1)
    {
        int d;
        scanf("%d", &d);
        if(d == 0)
            break;
        //创建新节点并赋值
        struct Node*pnew = Create_Node(d);
        if(pnew == NULL)
            return NULL;

        //将新节点增加到链表中
        if(first == NULL && last == NULL)//空链表
        {
            first = last = pnew;
        }
        else
        {
            //查找第一个比pnew大的节点
            struct Node* p = first;
            struct Node*pre = NULL;
            while(p)
            {
                if(p->data > pnew->data)
                    break;
                pre = p;
                p = p->next;
            }
            if(p)
            {
                if(p == first)
                {
                    pnew->next = first;
                    first = pnew;
                }
                else
                {
                    pnew->next = p;
                    pre->next = pnew;
                }
            }
            else
            {
                last->next = pnew;
                last = pnew;
            }
        }
    }

   return first;
}

/*
	Reverse_LinkedList:就地逆序一条单链表(不可额外开辟节点空间)
	返回值：
		返回逆序之后首节点指针
*/
struct Node*Reverse_LinkedList_1(struct Node*first)
{
    struct Node*first_new = NULL;
    while(first)
    {
        //截取原链表中首节点
        struct Node*pnew = first;
        first = first->next;
        pnew->next = NULL;

        //以头插法方式增加到逆转链表上
        if(first_new == NULL)
        {
            first_new = pnew;
        }
        else
        {
            pnew->next = first_new;
            first_new = pnew;
        }
    }

    return first_new;
}
/*
	Reverse_LinkedList:就地逆序一条单链表(不可额外开辟节点空间)
	返回值：
		返回逆序之后首节点指针
*/
struct Node*Reverse_LinkedList_2(struct Node*first)
{
    struct Node*p = first;
    struct Node*pre = NULL;//

    while(first)
    {
        p = first;
        first = first->next;
        p->next = pre;
        pre = p;
    }
    
    return p;
   
}

